#include "global.h"
#include <cmath>
#include <algorithm>

const double PI = acos(-1.0);
double Kn[MAX_TIME_SLICING*2];
double num_read_for_gather[MAX_TAG_NUM][MAX_TIME_SLICING];

namespace FFT{
    /*快速傅里叶变换*/
    const int limit = 262144, fft_k = 18;
    int rev[limit];
    
    struct Complex{
        double x,y;
        Complex(double a=0,double b=0):x(a),y(b){}
        Complex operator=(const int b){
            *this=Complex(b,0);
            return *this;
        }
        Complex operator+(const Complex b){
            return Complex(x+b.x,y+b.y);
        }
        Complex operator-(const Complex b){
            return Complex(x-b.x,y-b.y);
        }
        Complex operator*(const Complex b){
            return Complex(x*b.x-y*b.y,x*b.y+y*b.x);
        }
        Complex operator*=(const Complex b){
            *this=*this*b;
            return *this;
        }
    };

    void init_fft(){
        for (int i=0; i<limit;i++)
            rev[i]=(rev[i>>1]>>1)|((i&1)<<(fft_k-1));
    }
    void fft(Complex *a,int type){
        for(int i=0;i<limit;i++)
            if(i<rev[i])
                swap(a[i],a[rev[i]]);
        for(register int mid=1;mid<limit;mid<<=1){
            const double x=PI/mid;
            Complex wn=Complex(cos(x),sin(x));
            for(register int R=mid<<1,j=0;j<limit;j+=R){
                Complex w=Complex(1,0);
                for(register int k=0;k<mid;k++,w*=wn){
                    Complex y=a[j+k],z=w*a[j+mid+k];
                    a[j+k]=y+z;
                    a[j+mid+k]=y-z;
                }
            }
        }
        if(type==-1){
            reverse(a+1,a+limit);
            for(int i=0;i<=limit;i++)
                a[i].x/=limit;
        }
        return;
    }
}

FFT::Complex a[FFT::limit], b[FFT::limit], c[FFT::limit];

double value[MAX_TAG_NUM][MAX_TIME_SLICING];

void gather_action()
{
    /*
        在round2前利用注意力机制实现为未知tag分配tag。整个项目的目标是尽快读取尽可能多的文件，所以尽量要让读请求相似的数据
    放在一起。而我们的写策略会把tag相同的放在一起，所以也就是让读请求相似的数据具有相同的tag。可以令每个数据的读取请求发生
    时间片为x，某个tag的所有已知数据的读取请求发生在时间片i的数量为y_i，那么可以利用注意力汇聚将它的注意力集中在该请求附近
    的对应tag的读取请求量。但是直接套用注意力汇聚的公式时间上会爆炸，但是发现该公式形成了卷积的形式，所以可以使用快速傅里叶
    变换进行加速。
    */
    // FILE *file=fopen("tmp.txt","w");
    double w=0.012;
    for (int i = -MAX_TIME_SLICING + 1; i < MAX_TIME_SLICING; i++)
    {
        Kn[i + MAX_TIME_SLICING] = 1 / sqrt(PI) * exp(-(double)i * i * w * w / 2.0);
    }
    for(int i=0;i<MAX_TIME_SLICING*2;i++)
    {
        a[i] = FFT::Complex(Kn[i],0);
    }
    FFT::init_fft();
    FFT::fft(a,1);
    // for(int i=0;i<FFT::limit;i++)
    //     fprintf(file,"%.2lf ",a[i].x);
    // fprintf(file,"\n\n");
    for (int tag = 1; tag <= M; tag++)
    {
        for(int i=0;i<MAX_TIME_SLICING;i++)
        {
            b[i] = FFT::Complex(num_read_for_gather[tag][i],0);
        }
        for(int i=MAX_TIME_SLICING;i<FFT::limit;i++)
            b[i]=FFT::Complex(0,0);
        // for(int i=0;i<FFT::limit;i++)
        //     fprintf(file,"%.2lf ",b[i].x);
        // fprintf(file,"\n");
        FFT::fft(b,1);
        for(int i=0;i<FFT::limit;i++)
        {
            c[i] = a[i]*b[i];
        }
        FFT::fft(c,-1);
        // for(int i=0;i<FFT::limit;i++)
        //     fprintf(file,"%.2lf ",c[i].x);
        // fprintf(file,"\n");
        for(int i=1;i<=T+105;i++)
        {
            value[tag][i] = c[i+MAX_TIME_SLICING].x;
            // fprintf(file,"%.2lf ",value[tag][i]);
        }
        // fprintf(file,"\n\n");
    }
    for(int object_id=1;object[object_id].size;object_id++)
    {
        if(object[object_id].tag)
            continue;
        double ans=0;
        int tg=rand()%M+1;
        for(int tag=1;tag<=M;tag++)
        {
            double val=0;
            for(int i=object[object_id].last_request_point;i;i=request[i].prev_id)
            {
                // fprintf(stderr,"%d %d %d %.2lf\n",tag,i,request[i].burntime,value[tag][request[i].burntime]);
                val += value[tag][request[i].burntime];
            }
            // fprintf(stderr,"%.2lf ",val);
            if(val>ans)
            {
                // fprintf(stderr,"%.2lf %.2lf %d %d\n",val,ans,tg,tag);
                ans=val;
                tg=tag;
            }
        }
        object[object_id].tag=tg;
        // fprintf(file,"%d ",tg);
    }
    // fclose(file);
    return;
}